package leetcode_400;

/**
 *@author 周杨
 *IntegerReplacement_397 给定一个正整数  如果为奇数 就+1或者-1  如果为偶数 直接除以2 直至这个数为1  求最小步骤数
 *describe:用递归 AC 50%
 *2018年7月16日 上午9:47:40
 */
public class IntegerReplacement_397 {
	public static void main(String[] args) {
		IntegerReplacement_397 test=new IntegerReplacement_397();
		System.out.println(test.integerReplacement(7));
	}
	
	public int integerReplacement(int n) {
        return help(0,n);
    }
	
	public int help(int count,long n) {
		if(n==1)
			return count;
		if(n%2==0)
			return help(count+1,n/2);
		else {
			int res1=help(count+1,(n+1));
			int res2=help(count+1,(n-1));
			return  Math.min(res1, res2);
		}
	}
}
